package leetcode_500;

/**
 *@author 周杨
 *RemoveKDigits_402 给定一个字符串(一个很大的数字) 要求在移除k个字符的情况下 返回一个最小的数字
 *describe:用递归 每次减少一个字符 如果遇到前驱0 先删除  若遇到递减字符删除前一个 如果全是递增 则一次性删除到合法
 *AC 16%
 *2018年7月18日 下午7:26:57
 */
public class RemoveKDigits_402 {
	int finalLen=0;
	int count=0;
	int k;
	public static void main(String[] args) {
		//System.out.println("anb".substring(0, 1));
		RemoveKDigits_402 test=new RemoveKDigits_402();
		System.out.println(test.removeKdigits("10200", 2));
		System.out.println(test.removeKdigits("1432219", 3));
		System.out.println(test.removeKdigits("12034567", 2));

	}
	public String removeKdigits(String num, int k) {
		this.finalLen=num.length()-k;
		this.k=k;
		String res=help(num);
		return res.length()==0?"0":res;
    }
	
	public String help(String now) {
		if(now.startsWith("0"))
			return help(now.substring(1));
		if(count==k)
			return now;
		for(int i=0;i<now.length()-1;++i) {
			if(now.charAt(i)>now.charAt(i+1)) {
				++count;
				return help(now.substring(0, i)+now.substring(i+1));
			}
		}//全是递增
		return now.substring(0,finalLen);
	}
}
